package com.dyz.leetcode._20_dynamicProgramming._32;

public class longestValidParentheses01 {
    public int longestValidParentheses(String s) {
        int n = s.length();
        // 1. 状态，dp[i] 表示以下标为 i 的字符结尾的最长有效子字符串的长度
        int[] dp = new int[n];
        if(s.length()<=1){return 0;}
        dp[0] = 0;
        if(s.charAt(0)=='(' && s.charAt(1)==')'){dp[1]=2;}
        int res = dp[1];
        for (int i = 2; i <s.length() ; i++) {
            if(s.charAt(i)==')'){
                if(s.charAt(i-1)=='('){
                    dp[i] = dp[i - 2] + 2;
                }else if(i-dp[i-1]-1>=0 && s.charAt(i-dp[i-1]-1)=='('){
                    dp[i] = dp[i-1]+2+(i-dp[i-1]-2>=0?dp[i-dp[i-1]-2]:0);

                }
            }
            res = Math.max(res, dp[i]);
        }
        return res;
    }
}
